Image likeness, such as a correspondence between regions of one or more images, can be defined in many different implementations that depend on such correspondences. For example, this can include algorithms for correspondence in computer vision, such as wide baseline stereo matching and motion tracking, and graphics algorithms for image summarization, image completion, synthesizing textures, images and video, and others.
For example, a similarity score between images can be computed by a bidirectional similarity metric, which measures the distance from each patch in one image to the other image, and vice versa. A bidirectional similarity can be evaluated based on a patch distance metric. A bidirectional similarity computation can involve calculating nearest neighbor patches, which can be computationally demanding. Even with available approximation techniques, the bidirectional similarity calculation may not be quick enough for use in interactive applications for very large images. Moreover, approximation techniques may not be useable with certain distance metrics.